package fun.ticsmyc.dataStructure;


import org.junit.Test;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.dataStructure
 * @date 2020-08-13 21:11
 */
public class 链表反转 {

    /**
     * 递归反转
     * @param head
     * @return
     */
    public ListNode reverse1(ListNode head){
        if(head == null || head .next == null){
            return head;
        }
        ListNode temp  =reverse1(head.next);
        head.next.next = head;
        head.next = null;
        return temp;
    }

    /**
     * 迭代反转
     * @param head
     * @return
     */
    public ListNode reverse2(ListNode head){
        ListNode p = null;
        ListNode q = head;
        while(q != null){
            ListNode r = q.next;
            q.next = p;
            p=q;
            q=r;
        }
        return p;
    }


    /**
     * 反转前n个节点
     * @param head
     * @param n
     * @return
     */
    ListNode reverse = null;
    public ListNode reverseN(ListNode head, int n){
        if(n==1 || head == null || head.next == null){
            reverse = head.next;
            return head;
        }
        ListNode temp = reverseN(head.next, n-1);
        head.next.next = head;
        head.next = reverse;
        return temp;
    }


    /**
     * 反转一个区间
     * @param head
     * @param m
     * @param n
     * @return
     */
    public ListNode reverseBetween(ListNode head,int m , int n){
        if(m==1){
            return reverseN(head,n);
        }

        head.next =reverseBetween(head.next,m-1,n-1);
        return head;
    }

    /**
     * k个一组反转
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseEveryK(ListNode head , int k){
        ListNode tail = head;
        for(int i=1 ;i<k;++i){
            if(tail == null) {
                //不足k个 不反转
                return head;
            }
            tail= tail.next;
        }
        if(tail == null) {
            //不足k个 不反转
            return head;
        }
        ListNode nextHead = tail.next;
        ListNode newHead = reverseBetween(head,tail);
        head.next = reverseEveryK(nextHead,k);
        return newHead;
    }

    /**
     * 反转head tail之间的链表
     * @param head
     * @param tail
     * @return
     */
    private ListNode reverseBetween(ListNode head, ListNode tail){
        ListNode p = null;
        ListNode q = head;
        while(p != tail){
            ListNode temp = q.next;
            q.next = p;
            p=q;
            q=temp;
        }
        return p;
    }


    private ListNode reverseKGroup(ListNode head,int k){
        ListNode tail = head;
        for(int i =1; i<k && tail != null ; ++i){
            tail = tail.next;
        }
        if(tail ==null){
            return head;
        }
        ListNode nextList = tail.next;
        ListNode listNode = reverseN(head, k);

        head.next = reverseEveryK(nextList,k);
        return listNode;
    }

    /**
     * k个一组反转链表， 不足k个不反转
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup2(ListNode head, int k) {
        ListNode tail =head;
        for(int i=0;i<k;++i){
            if(tail ==null){
                //不足k个
                return head;
            }
            tail=tail.next;
        }
        ListNode p = reverseKGroup2(tail,k);
        ListNode q=head;
        while(q!= tail){
            ListNode r=q.next;
            q.next =p;
            p=q;
            q=r;
        }
        return p;
    }

    @Test
    public void test(){
        int[] arr = new int[] {1,2,3,4,5,6};
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        for(int a:arr){
            ListNode listNode = new ListNode(a);
            cur.next = listNode;
            cur=cur.next;
        }
        head=head.next;

        print(head);
        ListNode reverse = reverseKGroup(head,2);
        print(reverse);
    }


    private void print(ListNode head){
        while(head != null){
            System.out.print(head.val +" ");
            head = head.next;
        }
        System.out.println();
    }

    class ListNode{
        public ListNode next;
        public int val;
        public ListNode(int val){
            this.val = val;
            this.next = null;
        }
    }
}
